package data_structure.binary_tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)
 * 性质2：深度为k的二叉树至多有2k-1个结点（k>=1）
 * 性质3：包含n个结点的二叉树的高度至少为(log2n)+1
 * 性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
 */
public class BinaryTree {
    public BinaryTree left;
    public BinaryTree right;
    public BinaryTree root;
    //    数据域
    private Object data;
    //    存节点
    public List<BinaryTree> datas;

    public BinaryTree(BinaryTree left, BinaryTree right, Object data) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    //    将初始的左右孩子值为空
    public BinaryTree(Object data) {
        this(null, null, data);
    }

    public BinaryTree() {
    }

    /**
     * 树的创建
     */
    public void creat(Object[] objs) {
        datas = new ArrayList<>();
        //将一个数组的值依次转换为Node节点
        for (Object o : objs) {
            datas.add(new BinaryTree(o));
        }
        //第一个数为根节点
        root = datas.get(0);
        //建立二叉树
        for (int i = 0; i < objs.length / 2; i++) {
            //左孩子
            datas.get(i).left = datas.get(i * 2 + 1);
            //右孩子
            if (i * 2 + 2 < datas.size()) {
                //避免偶数的时候 下标越界
                datas.get(i).right = datas.get(i * 2 + 2);
            }
        }
    }

    /**
     * 先序遍历
     */
    public void preorder(BinaryTree root) {
        if (root != null) {
            System.out.print(root.data + "\t");
            preorder(root.left);
            preorder(root.right);
        }

    }

    /**
     * 中序遍历
     */
    public void inorder(BinaryTree root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + "\t");
            inorder(root.right);
        }

    }

    /**
     * 后序遍历
     */
    public void afterorder(BinaryTree root) {
        if (root != null) {
            System.out.print(root.data + "\t");
            afterorder(root.left);
            afterorder(root.right);
        }

    }
}
